package com.caochenlei.graph;

import java.util.Stack;

public class BellmanFordSP {
    private DirectedEdge[] edgeTo;          //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private double[] distTo;                //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    private boolean hasNegativeCycle;       //是否含有负权重环，所有边进行N-1次松弛后，若还可以松弛，则存在

    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        //初始化edgeTo
        this.edgeTo = new DirectedEdge[G.size()];
        //初始化distTo
        this.distTo = new double[G.size()];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0D;
        //对图中所有边进行N-1次松弛
        for (int i = 0; i < G.size(); i++) {
            for (DirectedEdge edge : G.edges()) {
                relax(edge);
            }
        }
        //判断图中是否含有负权重环
        for (DirectedEdge edge : G.edges()) {
            if (relax(edge)) {
                hasNegativeCycle = true;
                return;
            }
        }
    }

    //边的松弛
    private boolean relax(DirectedEdge e) {
        int v = e.from();
        int w = e.to();
        if (distTo(w) > distTo(v) + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            return true;    //松弛成功
        }
        return false;       //松弛失败
    }

    //判断图中是否含有负权重环
    public boolean hasNegativeCycle() {
        return hasNegativeCycle;
    }

    //获取从顶点s到顶点v的最短路径的总权重
    public double distTo(int v) {
        return distTo[v];
    }

    //判断从顶点s到顶点v是否可达
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //找出从起点s到顶点v的路径
    public Stack<DirectedEdge> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<DirectedEdge> path = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }
}
